Data Structure Libraries in C++.
----------------------------
// This C++ code not runstd::cout << "Welcome to our website";
Page page;
page.Run();
My social network
[Github]
[Facebook]
[Battle caro with me on Facebook uwu]
Documentation : DSACPP
Return multiple values.
Assign multiple values to multiple variables.
Alternative to struct.
The more tuple types declared, the larger the program source code.
Don't have support iterator.
Search with keyword : Variadic Templates.
Learning from Python's 'range' class.
For loop with 'range', easy to used.
Speed up for loop with reference variable.
Search with keyword : Range of Python.
Create heap from any container.
Sort any container using heap.
Build-heap with static method.
Search with keyword : Heap Array.
Containers operate on the principle of last in, first out.
Stores a linked list of variables of the same type.
Alternative to recursion.
Depth First Search.
Search with keyword : Stack.
Containers operate on the principle of first in, first out.
Stores a linked list of variables of the same type.
Breadth First Search.
Search with keyword : Queue.
Stores a contiguous sequence of variables of the same type.
Support important methods on Array List.
Speed up methods involving swap.
Search with keyword : Dynamic Array.
Stores a key and value pair.
Allow access to attributes, can change value.
Used in map.
Search with keyword : Pair in C++.
Are containers that store unique elements following a ascending order.
Allow access to element by index.
Fast insert, delete and search speed.
Support iterator.
Search with keyword : B+ Tree.
Are associative containers that store elements formed by a combination of a key value and a mapped value, following a specific order.
Allow access to element by key or index.
Fast insert, delete and search speed.
Support iterator.
Search with keyword : B+ Tree.
Are containers that store unique elements in no particular order, and which allow for fast retrieval of individual elements based on their value.
Fast insert, delete and search very speed.
Support iterator.
Don't have support access to element by index.
Search with keyword : Hash Table.
Are associative containers that store elements formed by the combination of a key value and a mapped value, and which allows for fast retrieval of individual elements based on their keys.
Fast insert, delete and search very speed.
Support iterator.
Allow access to element by key.
Don't have support access to element by index.
Search with keyword : Hash Table.
Documentation : Tuple
[Back] [Source]std::cout << tup;
// (5, c, World)
std::cout << get<1>(tup); // c std::cout << tup.len(); // 3
Cannot change the value of elements inside the tuple.
return tuple<int, int>(x1 + x2, y1 + y2);
}
Return a tuple containing different values.
tuple<int, int >(1, 5).convert(x , y);
Use the 'convert' method to assign values to multiple variables, the number of variables equal to the number of elements in the tuple.
tuple<int , int, int>(a, b, c). convert(a, b, c)
// a = 5, b = 2, c = 3
Use the 'convert' method to swap in any order.
Documentation : Range
[Back] [Source]std::cout << ran; // (0, 5, 2)
With start = 0, end = 5, step = 2.
std::cout << i << ' ';
// 0 1 2 3 4
for(int i : range(2, 5))
std::cout << i << ' ';
// 2 3 4
for(int i : range(0, 5, 2))
std::cout << i << ' ';
// 0 2 4
Documentation : Heap
[Back] [Source]std::cout << heap1;
// [1, 4, 2, 5, 6]
int a[]{2, 5, 1, 4, 6};
maxheap<int> heap2(a, a + 5);
std::cout << heap2;
// [6, 2, 1, 4, 5]
Don't name the variable 'heap' because there is already a class named 'heap'.
The cost of creating heap from another container is O(n log n), but O(n) if that is the best case.
minheap<int> heap1(a, a + n);
for(int i = 0; i < n; ++i)
a[i] = heap1.pop();
for(int i : a)
std::cout << i << ' ';
// 1 2 4 5 6
Time complexity of creating heap from another container is O(n log n), but O(n) if that is the best case.
auto less_than = [](int x, int y){ return x < y; }; heap<int>::build_heap(a, n, less_than);
for(int i : a)
std::cout << i << ' '; // 1 4 2 5 6
Build min heap by static method of heap class using less_than function, time complexity is O(n log n) or O(n).
| Methods | Time Complexity | ||
|---|---|---|---|
| Worst | Average | Best | |
| push | O(n) | O(log n) | O(1) |
| pop | O(n) | O(log n) | |
| try_pop | O(n) | O(log n) | |
| top | O(1) | ||
| clear | O(n) | ||
| out | O(n) | ||
| empty | O(1) | ||
| swap | O(1) | ||
| operator bool | O(1) | ||
| operator= | O(n) | O(1) | |
| operator>> | O(n) | O(log n) | O(1) |
| operator<< | O(n) | O(log n) | |
| begin | O(1) | ||
| end | O(1) | ||
| rbegin | O(1) | ||
| rend | O(1) | ||
| cbegin | O(1) | ||
| cend | O(1) | ||
| crbegin | O(1) | ||
| crend | O(1) | ||
Documentation : Stack
[Back] [Source]for(int i = 0; i < 5; ++i)
st.push(i);
std::cout << st;
// [4, 3, 2, 1, 0]
The last input element is added to the top.
std::cout << i << ' ';
// 4 3 2 1 0
| Methods | Time Complexity | ||
|---|---|---|---|
| Worst | Average | Best | |
| push | O(1) | ||
| pop | O(1) | ||
| try_pop | O(1) | ||
| top | O(1) | ||
| clear | O(n) | ||
| out | O(n) | ||
| empty | O(1) | ||
| swap | O(1) | ||
| operator bool | O(1) | ||
| operator= | O(n) | O(1) | |
| operator>> | O(1) | ||
| operator<< | O(1) | ||
| begin | O(1) | ||
| end | O(1) | ||
Documentation : Queue
[Back] [Source]for(int i = 0; i < 5; ++i)
qu.push(i);
std::cout << qu;
// [0, 1, 2, 3, 4]
The last input element is added at the end.
std::cout << i << ' ';
// 0 1 2 3 4
| Methods | Time Complexity | ||
|---|---|---|---|
| Worst | Average | Best | |
| push | O(1) | ||
| pop | O(1) | ||
| try_pop | O(1) | ||
| top | O(1) | ||
| bottom | O(1) | ||
| clear | O(n) | ||
| out | O(n) | ||
| empty | O(1) | ||
| swap | O(1) | ||
| operator bool | O(1) | ||
| operator= | O(n) | O(1) | |
| operator>> | O(1) | ||
| operator<< | O(1) | ||
| begin | O(1) | ||
| end | O(1) | ||
Documentation : Array List
[Back] [Source]std::cout << list;
// [2, 5, 1, 3, 7, 4]
arraylist<int> list2(list.begin(), list.end());
std::cout << list2;
// [2, 5, 1, 3, 7, 4]
Time complexity of creating heap from another container is O(n).
Create Array List from any container by using iterator of this container, time complexity depends on the speed of that iterator.
std::cout << list;
// [2, 5, 1, 3, 7, 4]
for(int i : list)
std::cout << i << ' ';
// 2 5 1 3 7 4
Time complexity of creating heap from another container is O(n).
Create Array List from any container by using iterator of this container, time complexity depends on the speed of that iterator.
| Methods | Time Complexity | ||
|---|---|---|---|
| Worst | Average | Best | |
| push | O(n + k) | O(k) | |
| pushBack | O(n) | O(1) | |
| pushFront | O(n) | ||
| pushAt | O(n + k) | O(k) | |
| popBack | O(n) | O(1) | |
| popFront | O(n) | ||
| popAt | O(n + k) | O(k) | |
| pop | O(n) | ||
| popAll | O(n) | ||
| popIn | O(n) | ||
| indexOf | O(n) | ||
| binSearch | O(log n) | ||
| reverse | O(n) | ||
| memset | O(n) | ||
| clear | O(n) | ||
| swap | O(1) | ||
| count | O(n) | ||
| foreach | O(n) | ||
| selectIf | O(n) | ||
| all | O(n) | ||
| any | O(n) | ||
| sort | O(n2) | O(n log n) | |
| out | O(n) | ||
| len | O(1) | ||
| empty | O(1) | ||
| operator bool | O(1) | ||
| operator= | O(n) | O(1) | |
| operator+= | O(n) | ||
| operator+ | O(n) | ||
| begin | O(1) | ||
| end | O(1) | ||
| rbegin | O(1) | ||
| rend | O(1) | ||
| cbegin | O(1) | ||
| cend | O(1) | ||
| crbegin | O(1) | ||
| crend | O(1) | ||
Documentation : Pair
[Back] [Source]std::cout << pa;
// (abc, 5)
std::cout << pa.key << ' ' <<pa.value;
// abc 5
Attributes of Pair are 'key' and 'value', you can change value of these.
Documentation : Set
[Back] [Source]std::cout << tree;
// [0, 1, 2, 3, 5, 8]
int a[]{0, 1, 0, 2, 2, 7, 4};
set<int> tree1(a, a + 7);
std::cout << tree1;
// [0, 1, 2, 4, 7]
Elements in ascending order, don't duplicates.
Time complexity of creating Set from other Set is O(n).
std::cout << i << ' ';
// 0 1 2 3 5 8
| Methods | Time Complexity | ||
|---|---|---|---|
| Worst | Average | Best | |
| push | O(log n) | ||
| pop | O(log n) | ||
| contains | O(log n) | ||
| clear | O(n) | ||
| swap | O(1) | ||
| out | O(n) | ||
| empty | O(1) | ||
| len | O(1) | ||
| operator bool | O(1) | ||
| operator[] | O(log n) | ||
| operator() | O(log n) | ||
| operator= | O(n) | O(1) | |
| begin | O(1) | ||
| end | O(1) | ||
| rbegin | O(1) | ||
| rend | O(1) | ||
| cbegin | O(1) | ||
| cend | O(1) | ||
| crbegin | O(1) | ||
| crend | O(1) | ||
Documentation : Map
[Back] [Source]map<char, int> tree{pa('a', 8), pa('B', 2), pa('5', 4)};
std::cout << tree;
// [5 : 4, B : 2, a : 8]
Elements in ascending order by key, don't key duplicates.
Time complexity of creating Map from other Map is O(n).
std::cout << i << ' ';
// (5, 4)
// (B, 2)
// (a, 8)
| Methods | Time Complexity | ||
|---|---|---|---|
| Worst | Average | Best | |
| push | O(log n) | ||
| pop | O(log n) | ||
| contains | O(log n) | ||
| clear | O(n) | ||
| swap | O(1) | ||
| out | O(n) | ||
| empty | O(1) | ||
| len | O(1) | ||
| operator bool | O(1) | ||
| operator[] | O(log n) | ||
| operator() | O(log n) | ||
| operator= | O(n) | O(1) | |
| begin | O(1) | ||
| end | O(1) | ||
| rbegin | O(1) | ||
| rend | O(1) | ||
| cbegin | O(1) | ||
| cend | O(1) | ||
| crbegin | O(1) | ||
| crend | O(1) | ||
Documentation : Hash Set
[Back] [Source]std::cout << hash;
// [1, 2, 5, 6, 7, 8, -5]
int a[]{5, 1, 1, -5, 2, 7, 6, 8};
hashset<int> hash1(a, a + 8);
std::cout << hash1;
// [1, 2, 5, 6, 7, 8, -5]
Time complexity of creating Hash Set from another container is O(n).
std::cout << i << ' ';
// 1 2 5 6 7 8 -5
for(auto i = hash.rbegin(); i != hash.rend(); --i)
std::cout << *i << ' ';
// -5 8 7 6 5 2 1
| Methods | Time Complexity | ||
|---|---|---|---|
| Worst | Average | Best | |
| push | O(n) | O(1) | |
| pop | O(n) | O(1) | |
| contains | O(n) | O(1) | |
| clear | O(n) | ||
| swap | O(1) | ||
| out | O(n) | ||
| empty | O(1) | ||
| len | O(1) | ||
| operator bool | O(1) | ||
| operator[] | O(n) | O(1) | |
| operator= | O(n) | O(1) | |
| begin | O(n) | O(1) | |
| end | O(1) | ||
| rbegin | O(n) | O(1) | |
| rend | O(1) | ||
| cbegin | O(n) | O(1) | |
| cend | O(1) | ||
| crbegin | O(n) | O(1) | |
| crend | O(1) | ||
Documentation : Hash Map
[Back] [Source]hashmap<char, int> hash{pa('D', 6), pa('t', 1), pa('0', 0)};
std::cout << hash;
// [t : 1, D : 6, 0 : 0]
hashset<int> hash1(hash.begin(), hash.end());
std::cout << hash1;
// [t : 1, D : 6, 0 : 0]
Time complexity of creating Hash Set from another container is O(n).
std::cout << i;
// (t : 1)
// (D : 6)
// (0 : 0)
| Methods | Time Complexity | ||
|---|---|---|---|
| Worst | Average | Best | |
| push | O(n) | O(1) | |
| pop | O(n) | O(1) | |
| contains | O(n) | O(1) | |
| clear | O(n) | ||
| swap | O(1) | ||
| out | O(n) | ||
| empty | O(1) | ||
| len | O(1) | ||
| operator bool | O(1) | ||
| operator[] | O(n) | O(1) | |
| operator= | O(n) | O(1) | |
| begin | O(n) | O(1) | |
| end | O(1) | ||
| rbegin | O(n) | O(1) | |
| rend | O(1) | ||
| cbegin | O(n) | O(1) | |
| cend | O(1) | ||
| crbegin | O(n) | O(1) | |
| crend | O(1) | ||
Overlord Opening IV
00:00 -[Prev] [Play] [Next] [Loop]